Paya Lebar là một vùng đầm lầy rộng lớn gần với Sông Kallang. Trong tiếng Mã Lai, Paya nghĩa là "đầm lầy" và lebar nghĩa là "rộng lớn". Đây là một quận mới mở rộng, khét tiếng bởi nạn chiếm cư bất hợp pháp với các cư dân sinh sống bằng nghề trồng trọt và chăn nuôi heo và gia cầm.

Một trong những người thiết lập chế độ thuộc địa đầu tiên ở vùng đất này là Richard Owen Norris (mất năm 1905). Ông đã mua một phần đất của khu vực này vào năm 1865 để sống với gia đình.

Năm 1915, một đài phát thanh hải quân được xây dựng tại quận này.

Năm 1955, Sân bay Quốc tế Singapore (thường được biết với tên gọi "Sân bay Paya Lebar") được khánh thành và trở thành một điểm mốc quan trọng của vùng này, cùng với các công trình nhà ở, trường học và nhà máy khác.

Đường Paya Lebar Street được chính thức đặt tên vào năm 1958 trong khi một con đường cùng tên khác Paya Lebar Way chính thức xuất hiện năm 1972.